package Algorithm.greedyAlgorithm;

/**
 * 860. 柠檬水找零 https://leetcode.cn/problems/lemonade-change
 * 题目简述：初始手头没钱，顾客依次排队买水，每位顾客只买一杯柠檬水，然后向你付5美元、10美元或20美元其中一种，bills[i]是第i位顾客付的账，判断每次能否正确找零
 */
public class LemonadeChange {

    public static void main(String[] args) {
        new LemonadeChange().lemonadeChange(new int[]{5,5,5,20,5,5,5,20,5,5,5,10,5,20,10,20,10,20,5,5});
    }

    /**
     * 思路：用一个大小为3的数组记录每种钞票的数量，然后每次尽量先用较大额钞票找零
     */
    public boolean lemonadeChange(int[] bills) {
        //用一个大小为3的数组记录每种钞票的数量
        int[] cashier = new int[2];
        for(int i=0;i < bills.length;i++) {
            if(bills[i] == 5) {
                cashier[0]++;
            } else if(bills[i] == 10) {
                if(cashier[0]-- <= 0) return false;
                cashier[1]++;
            } else if(bills[i] == 20) {
                if(cashier[1] > 0 && cashier[0] > 0) {
                    cashier[1]--;
                    cashier[0]--;
                } else if(cashier[0] > 2) {
                    cashier[0] = cashier[0] - 3;
                } else return false;
            }
        }
        return true;
    }
}
